package william.mergesort;

/**
 * @author ZhangShenao
 * @date 2024/1/26
 * @description <a href="https://leetcode.cn/problems/sort-an-array/description/">...</a>
 */
public class Leetcode912_排序数组 {
    /**
     * 采用归并排序实现
     */
    public int[] sortArray(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return nums;
        }

        //调用递归处理
        sortArrayRecursion(nums, 0, nums.length - 1);

        //返回排好序的数组
        return nums;
    }

    /**
     * 递归处理
     * 将数组nums[L,R]范围内处理成有序
     */
    private void sortArrayRecursion(int[] nums, int L, int R) {
        //递归终止条件
        if (L == R) {
            return;
        }

        //找到数组中点,将整体数组划分成左、右两个部分
        int M = L + ((R - L) >> 1);

        //分别将左、右两个数组处理成有序
        sortArrayRecursion(nums, L, M);
        sortArrayRecursion(nums, M + 1, R);

        //将两个有序数组合并成一个整体有序数组
        merge(nums, L, M, R);
    }

    /**
     * 合并操作
     * 将nums[L,M]和nums[M+1,R]两个有序数组,合并成一个整体有序数组
     */
    private void merge(int[] nums, int L, int M, int R) {
        //声明一个临时数组用于元素拷贝
        int len = R - L + 1;
        int[] tmp = new int[len];

        //初始化索引
        int l = L;
        int r = M + 1;
        int i = 0;

        //逐一比较左、右数组中的当前元素,将较小的元素拷贝到临时数组,并移动对应的指针
        while (l <= M && r <= R) {
            if (nums[l] <= nums[r]) {
                tmp[i++] = nums[l++];
            } else {
                tmp[i++] = nums[r++];
            }
        }

        //当其中一个数组已经拷贝完成,则直接拷贝另一个数组
        while (l <= M) {
            tmp[i++] = nums[l++];
        }
        while (r <= R) {
            tmp[i++] = nums[r++];
        }

        //最后将临时数组拷贝回原数组
        for (i = 0; i < len; i++) {
            nums[L + i] = tmp[i];
        }
    }
}
